Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Insufficient Nodes in Root to Leaf Paths

Problem Statement

Given the root of a binary tree and an integer limit, remove all insufficient nodes from the tree, and return the root of the updated tree.

A node is insufficient if all root to leaf paths that include this node leads to a sum less than the limit. If a node is removed, all its descendants should also be removed.

A leaf is a node with no children.

Examples

Example 1:

  • Input: root = [5, 3, 8, 2, -1, null, 10], limit: 15
Image
  • Expected Output: [5, null, 8, null, 10]
  • Explanation: The initial tree has 6 nodes. The path from the root 5 -> 3 -> 2 has a sum of 10 and path from the root 5 -> 3 -> -1 has a sum 7. So, node 3 and its children will be removed.

Example 2:

  • Input: root = [5, 4, 8, 11, null, 17, 4, 7, null, null, 5, 9], limit: 22
Image
  • Expected Output: [5,4,8,11,null,17,4,7,null,null,5,9]
  • Explanation: All 3 root to leaf paths have sum greater than 22. So, we don't need to remove any nodes.

Example 3:

  • Input: root = [10, 5, 15, 2, null, null, 20, -10, null, null, 25], limit: 15
Image
  • Expected Output: [10,null,15,null,20,null,25]
  • Explanation: The path from the root to the leaf through node 5 sums to 7, which is less than 15. Therefore, node 5 and its subtree are also removed.

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • -105 <= Node.val <= 105
  • -109 <= limit <= 109

Solution

To solve this problem, we use a Depth-First Search (DFS) approach to traverse the binary tree from the root to the leaves. The main idea is to keep track of the cumulative sum of node values along each path and compare it to the given limit. If a node is part of a path where the total sum from the root to that node is less than the limit and all paths through that node lead to a sum below the limit, the node and its subtree are pruned. We recursively process both the left and right subtrees of each node. After processing, if both subtrees of a node are pruned, the node itself is pruned.

This method ensures that only the nodes that contribute to a path with a sum greater than or equal to the limit are retained in the tree. This approach is effective because it guarantees that we consider all possible root-to-leaf paths, ensuring the tree is pruned optimally based on the given limit.

Step-by-Step Algorithm

  1. Define the base case:

    • Check if the current node (node) is null.
    • If node is null, return null. This handles the scenario where a subtree is empty.
  2. Update the current sum:

    • Add the value of the current node (node.val) to the ongoing sum (currentSum).
  3. Check if the current node is a leaf node:

    • A node is considered a leaf if both its left and right children are null.
    • If the node is a leaf, compare the updated currentSum with the limit:
      • If currentSum is less than limit, return null to prune this node.
      • If currentSum is greater than or equal to limit, return the node itself to keep it in the tree.
  4. Recursively process the left subtree:

    • Call the DFS function on the left child of the current node with the updated currentSum and the given limit.
    • Assign the result of this recursive call to node.left. This will prune or keep the left subtree based on the sum.
  5. Recursively process the right subtree:

    • Call the DFS function on the right child of the current node with the updated currentSum and the given limit.
    • Assign the result of this recursive call to node.right. This will prune or keep the right subtree based on the sum.
  6. Check if both left and right subtrees are pruned:

    • After the recursive calls, check if both node.left and node.right are null.
    • If both are null, it means all paths from this node do not meet the limit, so return null to prune this node.
  7. Return the current node:

    • If the node is not pruned, return the current node to keep it as part of the valid path in the tree.

Algorithm Walkthrough

Let’s walk through the algorithm with the example tree [5, 3, 8, 2, -1, null, 10] and a limit of 15.

  • Initial Tree:

        5
       / \
      3   8
     / \   \
    2  -1  10
    
  • Limit: 15

Step 1: Start DFS at the root node (5).

  • Current sum: 0 + 5 = 5
  • Node is not a leaf (it has children), so proceed to its subtrees.

Step 2: Process the left subtree (rooted at 3).

  • Current sum: 5 + 3 = 8
  • Node is not a leaf, so continue to its subtrees.

Step 3: Process the left child of 3 (node 2).

  • Current sum: 8 + 2 = 10
  • Node 2 is a leaf. Check if currentSum < limit.
  • 10 < 15 is true, so prune node 2 by returning null.

Step 4: Process the right child of 3 (node -1).

  • Current sum: 8 + (-1) = 7
  • Node -1 is a leaf. Check if currentSum < limit.
  • 7 < 15 is true, so prune node -1 by returning null.

Step 5: Check the node 3 after processing both children.

  • Both left and right subtrees of node 3 are pruned (node.left = null, node.right = null).
  • Prune node 3 by returning null.

Step 6: Process the right subtree (rooted at 8).

  • Current sum: 5 + 8 = 13
  • Node is not a leaf, so continue to its subtrees.

Step 7: Process the left child of 8 (which is null).

  • The node is null, return null.

Step 8: Process the right child of 8 (node 10).

  • Current sum: 13 + 10 = 23
  • Node 10 is a leaf. Check if currentSum < limit.
  • 23 >= 15 is true, so keep node 10 by returning it.

Step 9: Check the node 8 after processing both children.

  • Left subtree is pruned (node.left = null).
  • Right subtree is kept (node.right = node 10).
  • Keep node 8 by returning it.

Step 10: Check the root node 5 after processing both subtrees.

  • Left subtree is pruned (node.left = null).
  • Right subtree is kept (node.right = node 8).
  • Keep node 5 by returning it.

Final Pruned Tree:

  5
   \
    8
     \
     10
Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The algorithm performs a depth-first search (DFS) through the binary tree, visiting each node exactly once. Therefore, the time complexity is , where N is the number of nodes in the tree. This is because each node is processed only once during the DFS traversal.

Space Complexity

The space complexity is determined by the recursion stack in the DFS. In the worst case, the space complexity will be , where H is the height of the tree. In the worst case (unbalanced tree), H can be equal to N, making the space complexity . In a balanced tree, H would be , making the space complexity .

Insufficient Nodes in Root to Leaf Paths (medium)
Smallest String Starting From Leaf (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Complexity Analysis

Time Complexity

Space Complexity